Tháng 11 năm 1988, sau khi tốt nghiệp sĩ quan không quân ở Krasnodar, Liên Xô, Phạm Trường Sơn trở về Việt Nam, nhận quân hàm Trung úy, là Phi công của Trung đoàn 937, Sư đoàn 370, Quân chủng Phòng không – Không quân. Trong giai đoạn 1988–2003, ông là phi công phản lực lái máy bay chiến đấu Su-22, Sukhoi Su-30MKK, tiêm kích đa năng, lần lượt thăng quân hàm Trung úy, Thượng úy, Đại úy, Thiếu tá, giữ các chức Biên đội trưởng Phi đội 1, Phi đội 2, rồi Phó Phi đội trưởng Phi đội 2 của Trung đoàn 937.[2] Vào tháng 9 năm 2003, ông thăng quân hàm Trung tá, là Phó Bí thư Chi bộ, Phi đội trưởng Phi đội 2, Trung đoàn 937, sau đó 3 năm, tháng 11 năm 2008 thì là Thượng tá, Phó Trung đoàn trưởng kiêm Tham mưu trưởng, rồi Trung đoàn trưởng, Ủy viên Thường vụ Đảng ủy, Phó Bí thư Đảng ủy Trung đoàn 937. Tháng 4 năm 2011, ông được bổ nhiệm làm Phó Sư đoàn trưởng kiêm Tham mưu trưởng Sư đoàn 370, rồi thăng quân hàm Đại tá, thăng chức Sư đoàn trưởng, Ủy viên Thường vụ Đảng ủy, Phó Bí thư Đảng ủy Sư đoàn 370, đồng thời là Đảng ủy viên Đảng ủy Quân chủng Phòng không – Không quân. Sang cuối năm 2018, ông là Phó Tham mưu trưởng Quân chủng, Đảng ủy viên Đảng ủy Bộ Tham mưu Quân chủng.[3]

Tháng 12 năm 2019, Phạm Trường Sơn được được Thủ tướng Chính phủ Nguyễn Xuân Phúc bổ nhiệm làm Phó Tư lệnh Quân chủng Phòng không – Không quân, đồng thời được Chủ tịch nước Nguyễn Phú Trọng phong quân hàm Thiếu tướng. Năm 2021, với sự giới thiệu của Đảng ủy Quân chủng Phòng không – Không quân,[4] ông ứng cử đại biểu quốc hội từ Thừa Thiên Huế,[5] tại đơn vị bầu cử số 1 gồm thị xã Hương Trà và các huyện Phong Điền, Quảng Điền, A Lưới,[6] rồi trúng cử Đại biểu Quốc hội khóa XV với tỷ lệ 83,54%.[7] Ngày 20 tháng 8 năm 2022,[8] ông được bổ nhiệm làm Phó Tổng tham mưu trưởng Quân đội nhân dân Việt Nam.[9][10]